package main

import (
	"fmt"
	"strings"
)

/**
write a function to find the longest common prefix string amongst an array of strings.

写一个方法，找出字符串数组中最长的公共头字符串

*/

/**
方法1 水平扫描
![2017122015137001716026.png](http://cdn.bsummer.cn/2017122015137001716026.png)
*/

func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}

	prefix := strs[0]
	for i := 1; i < len(strs); i++ {
		for !strings.HasPrefix(strs[i], prefix) {
			prefix = prefix[:len(prefix)-1]
			fmt.Println(prefix)

			//不需要判断何时推出 prefix长度递减，兜底为"" 是一定可以跳出循环的
			//if len(prefix) == 0 {
			//	break
			//}
		}
	}

	return prefix
}

func find(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	prefix := strs[0]
	for i := 1; i < len(strs); i++ {
		for !strings.HasPrefix(strs[i], prefix) {
			prefix = prefix[:len(prefix)-1]
		}
	}
	return prefix
}

/**
方法2 先找最短字符串，然后轮训比较
*/
/*
func longestCommonPrefix(strs []string) string {

	//当字符串数组长度为0或1时直接返回
	if len(strs) == 0 {
		return ""
	} else if len(strs) == 1 {
		return strs[0]
	}

	//找出字符串数组中最短的字符串
	minLength := 10000
	minIndex := 0
	for k, v := range strs {
		if len(v) <= minLength {
			minLength = len(v)
			minIndex = k
		}
	}

	r := ""

	if strs[minIndex] == "" {
		return r
	}

	//遍历最小字符串，用每个字符与字符串数组中其他字符串对应位置的字符做比较 不相等跳出
	for k, v := range strs[minIndex] {
		fmt.Println(v, byte(v))
		for _, v2 := range strs {
			if v2[k] != byte(v) {
				return r
			}
		}
		r = r + string(v)
	}

	return r
}
*/

func main() {
	fmt.Println(longestCommonPrefix([]string{"aa", "abc", "abcd"}))
}
